Generally, in nodes of a wide area network (WAN) such as the Internet or a Metropolitan Area Network (MAN) some routing of information needs to be available so that any address encountered by a node of the network can be routed in a suitable direction. Traditional IP packet forwarding analyzes the destination IP address contained in the network layer header of each packet as the packet travels from its source to its final destination. A router analyzes the destination IP address independently at each hop in the network. Dynamic routing protocols or static configuration are used to build the database (the routing table) needed to analyze the destination IP address. Even in more complex routing schemes such as Multiprotocol Label Switching (“MPLS and VPN Architectures” Guichard and Pepelnjak, Cisco Press, 2001) this basic next hop address determination must be done. Due to the very large numbers of addresses required for a large network, especially a worldwide network such as the Internet, a node cannot store all the possible addresses and their next destinations efficiently. For example, the length of an IPv4 IP address is 32 bits and the length of an IPv6 address is 128 bits. Accordingly, there can be a theoretical maximum of 232 and 2128 addresses in an IPv4 or an Ipv6 router, respectively. These numbers are too large to store and search effectively via a look-up table or similar data structure.
Accordingly, it is standard practice to provide some form of matching algorithm so that. For example, for each address associated with a packet, a next routing destination is selected which is optimized in some way so that a reasonable next hop address can be found quickly. In other words a perfect match is not necessary. Thus, for any address, a search has to be made among the existing destination addresses to find an optimum next destination address in an optimum amount of time.
Consider an n-bit number D, which is the key for a search. The search database consists of an unordered list of prefixes Pi with associated result information. A prefix Pi is a combination of a prefix length k (1≦k≦n) and a k-bit number which can be defined as the value of the prefix Pi. A prefix P of length k matches a search key D, if and only if the most significant k bits of D equal the value of P.
The search of D against this database yields the single prefix P and its associated information that is the longest prefix which matches D, if there exists at least one matching prefix. This is the best matching prefix (or the longest matching prefix).
The difficulty in designing a best prefix match look-up at very high look-up speeds using standard memory components is in achieving various goals at the same time. Several desirable properties include: deterministic look-up speed regardless of search database size, limited small bounded number of memory accesses, fast and simple table construction and maintenance (insertion, withdrawal, update), efficient prefix storage, and all these properties regardless of the size of n.
A typical usage for a best prefix match lookup is in an Internet Protocol router. Incoming packets are forwarded to their next-hop router, based on the destination address of the packet. A crucial part of this forwarding decision is matching the destination address against the prefixes, which are stored in the routing table. In this usage, values for n are 32 (which corresponds to the length of an IPv4 IP address) or 128 (which corresponds to the length of an IPv6 address).